package cc.wsyw126.java.nowcoder.sword_offer;

import java.util.ArrayList;
import java.util.Collections;

/**
 * Created by Administrator on 2017/4/13.
 */
public class Permutation {
    private ArrayList<String> result = new ArrayList<>();
    public ArrayList<String> Permutation(String str) {
        if (str == null || str.length() == 0) return result;
        StringBuffer sb = new StringBuffer(str);
        doPermutation(sb, 0);
        Collections.sort(result);
        return result;
    }
    private void doPermutation(StringBuffer sb, int position) {
        if (position == sb.length()) {
            result.add(sb.toString());
            return;
        }
        for (int i = position; i < sb.length(); i++) {
            if (i != position && sb.charAt(i) == sb.charAt(position)) {
                continue;
            }
            char temp = sb.charAt(i);
            sb.replace(i,i+1,String.valueOf(sb.charAt(position)));
            sb.replace(position,position+1,String.valueOf(temp));
            doPermutation(sb, position+1);
            temp = sb.charAt(i);
            sb.replace(i,i+1,String.valueOf(sb.charAt(position)));
            sb.replace(position,position+1,String.valueOf(temp));
        }
    }

    public static void main(String[] args) {
        Permutation permutation = new Permutation();
        String b = "abca";
        ArrayList<String> permutation1 = permutation.Permutation(b);
        System.out.println(permutation1.size());
        for (String s : permutation1) {
            System.out.println(s);
        }
    }
}
